

/**
 * 
 * 任务处理
 * 
 * 题目描述

在某个项目中有多个任务（用task数组表示）需要你进行处理，其中：

task[i] = [si, ei]
你可以在 si ≤ day ≤ ei 中的任意一天处理该任务，请返回你可以处理的最大任务数。

输入描述
第一行为任务数量 n

1 ≤ n ≤ 100000
后面 n 行表示各个任务的开始时间和终止时间，使用 si，ei 表示

1 ≤ si ≤ ei ≤ 100000
输出描述
输出为一个整数，表示可以处理的最大任务数。

用例
输入	3
1 1
1 2
1 3
输出	3
说明	无

 */

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

/**
  * 
  题目解析
本题可以利用贪心思维+优先队列来求解。

我们可以将所有任务时间区间按照：优先按照结束时间降序，如果结束时间相同，则按照开始时间降序。这样排序的原因如下：

首先，任务优先按照结束时间降序后，那么第一个任务的结束时间就是最晚的（最大的），此时我们可以让第一个任务就在最晚时刻执行，如下面例子：

3
1 4
2 3
1 2
按照结束时间降序后：[1,4] , [2, 3],  [1, 2] ，第一个任务[1,4]在时刻4执行



这样做的好处是，避免第一个任务抢夺后面任务的执行时间，如下图所示：

如果第一个任务在时刻4执行，则第二个任务就有两个选择，时刻2或时刻3


如果第一个任务在时刻3执行，则第二个任务就只有一个选择，只能在时刻2执行


如果存在多个任务的结束时间都相同的话，则还需要对这些任务按照开始时间降序，这么做的原因是：

"时间长" 的任务 "可选执行时刻" 多
"时间短" 的任务 "可选执行时刻" 少
因此应该优先让时间跨度短的任务先执行，如下图所示：

如果优先时间短的任务，则三个任务都能执行


如果优先时间长的任务，则只能执行两个任务


但是上面逻辑是存在问题的，请看下面图示：

此时按照前面逻辑的话，只能执行三个任务



但是其实可以执行四个任务，执行策略如下：



主要问题是，当我们按照结束时间降序后，第一个任务选择时刻8执行完，此时后面三个任务的截止时间其实都是相同的，变为了时刻7。



因此，此时我们应该对后面三个任务重新按照时间跨度降序，再优先执行短的任务。

本题数量级较大，因此如果每次执行完一个任务，都对剩余任务进行更新结束时间，并重新排序的话，会超时。

改进策略是，使用优先队列，即：

如果当前任务的结束时间end >= 上一个任务的执行时刻last_end，则更新当前任务的结束为last_end - 1。如果 last_end - 1 > 当前任务开始时间start，则将当前任务重新入队排优先级。否则当前任务不可执行。
Java和Python有内置的优先队列类，而JS和C没有，因此JS和C需要手动实现一个优先队列，关于优先队列的实现原理请看：

LeetCode - 1705 吃苹果的最大数目-CSDN博客

经过测试，下面逻辑在本题数量级下会超时：

如果当前任务的结束时间end >= 上一个任务的执行时刻last_end，则更新当前任务的结束为last_end - 1。如果 last_end - 1 > 当前任务开始时间start，则将当前任务重新入队排优先级。否则当前任务不可执行。
因为，我们需要频繁更新任务的结束时间，并且入队出队。

为了避免频繁的更新任务结束时间，以及入队出队，我们可以做如下改动：

1、统计输入的所有任务的时间段，仅按照结束时间降序，得到数组ranges

2、定义一个优先队列pq，仅用于保存任务的开始时间（开始时间越大，优先级越高），我们可以认为优先队列中保存的任务（的开始时间）对应的结束时间都是相同的，我们定义这个公共结束时间为pq_end

3、遍历ranges，得到每一个任务的开始，结束时间range：[start, end]，然后比较遍历到任务的end 和 优先队列中所有任务的公共结束时间pq_end：

如果 end < pq_end，则在end ~ pq_end 这段间隔时间内，我们可以从pq中挑选出pq_end - end 个 较短任务进行执行，执行前需要检查 对应任务的开始时间 start <= pq_end，若不满足则不执行。每执行一个任务，则pq_end -= 1，count += 1（count是已执行的任务数量）。当pq_end == end时，则将当前遍历的任务的start 加入 优先队列。
具体过程如下图所示：




























  */
public class 任务处理 {
    
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
 
        int n = sc.nextInt();
    
        int[][] ranges = new int[n][2];
        for (int i = 0; i < n; i++) {
            ranges[i][0] = sc.nextInt();
            ranges[i][1] = sc.nextInt();
        }
    
        // 将所有任务按照结束时间降序
        Arrays.sort(ranges, (a, b) -> b[1] - a[1]);
    
        //优先队列中记录的是任务的开始时间，并且开始时间越大，优先级越高
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
    
        // 优先队列中记录的是结束时间相同的任务的开始时间，pq_end就是优先队列中任务的相同结束时间
        int pq_end = Integer.MAX_VALUE;
    
        // 最大任务数
        int count = 0;
    
        for (int[] range : ranges) {
        // 当前任务的开始和结束时间
        int start = range[0];
        int end = range[1];
    
        // 如果当前任务的结束时间 小于 优先队列中记录的任务的结束时间，则两个结束时间之间的间隔时间段，可以处理一些紧急任务
        while (pq.size() > 0 && end < pq_end) {
            // 这里的紧急任务即指时间短的任务，即开始时间比较大的任务
            if (pq.poll() <= pq_end) {
            // 如果紧急任务的开始时间未超过其结束时间，则可以执行
            count++;
            pq_end--; // 一个时刻只执行一个任务
            }
        }
    
        // 间隔时间消耗完后，优先队列中的任务的结束时间全部更新为当前任务的结束时间
        pq.add(start);
        pq_end = end;
        }
    
        // 收尾处理
        while (pq.size() > 0) {
            if (pq.poll() <= pq_end) {
                count++;
                pq_end--;
            }
        }
    
        System.out.println(count);
  }

}
